package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description 最大正方形 找到包含1的最大正方形 leetcode 第221题
 * @date 2023/10/6 17:07
 */
public class MaximalSquare {

    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;
        int maxSize = 0;

        int[][] dp = new int[row][column];
        for (int i = 0; i < row; i++) { //第i行0列的dp数组为初始值
            dp[i][0] = matrix[i][0] - '0';
            if (matrix[i][0] == '1') maxSize = 1;
        }
        for (int i = 0; i < column; i++) { //第0行i列的dp数组为初始值
            dp[0][i] = matrix[0][i] - '0';
            if (matrix[0][i] == '1') maxSize = 1;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                if(matrix[i][j] == '1') { //当前元素作为右下角 来衡量能构成的正方形的大小
                    int min_1 = Math.min(dp[i-1][j],dp[i][j-1]);
                    int min = Math.min(min_1,dp[i-1][j-1]);
                    dp[i][j] = min +1;

                    maxSize = Math.max(min+1,maxSize);
                }else{
                    dp[i][j] = 0;
                }
            }
        }

        return maxSize * maxSize;
    }

    public static void main(String[] args) {

    }
}
